import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author VernHe
 * @date 2021年07月02日 13:54
 */
public class Solution_0297 {
    /**
     * 序列化
     *
     * @param root
     * @return
     */
    public String serialize(TreeNode root) {
        String result = reserialize(root, "");
        System.out.println(result);
        return result;
    }

    /**
     * 反序列化
     *
     * @param data
     * @return
     */
    public TreeNode deserialize(String data) {
        // 先将字符串分割成数组
        String[] strings = data.split(",");
        List<String> list = new LinkedList(Arrays.asList(strings));
        // 遍历这个List，构建树
        return redeserialize(list);
    }

    /**
     * 递归进行序列化，先序遍历的顺序
     *
     * @param root
     * @param str
     * @return
     */
    private String reserialize(TreeNode root, String str) {
        if (root == null) {
            // 如果是 null 就拼接个 None
            str += "None,";
        } else {
            // 先拼接当前节点的值，接着再序列化左子树，然后再序列化右子树
            str += root.val + ",";
            System.out.printf("当前str为：" + str);
            str += reserialize(root.left, str);
            str += reserialize(root.right, str);
        }
        return str;
    }

    /**
     * 构建二叉树
     *
     * @param list
     * @return  根节点
     */
    private TreeNode redeserialize(List<String> list) {
        System.out.println("此时遍历: " + list.get(0));
        // 从头开始往后遍历
        if ("None".equals(list.get(0))) {
            // 如果是None就返回一个null节点
            list.remove(0);
            return null;
        }
        // 不是None就新键一个节点保存值，然后继续构建它的左子树和右子树
        TreeNode node = new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        node.left = redeserialize(list);
        node.right = redeserialize(list);
        return node;
    }

}
